单调栈的一些应用

单调栈的应用

单调栈的总结

运用单调栈，可以在一组元素中确定元素向左向右可以扩展的最大长度,这个元素一定是这段区间内的最大(小)值，与具体的入栈出栈规则有关。
可以确定的是：

• 如果一个元素入栈，则一定可以确定它在这个数组中的单调左边界;
• 如果一个元素出栈，则一定可以确定它在这个数组中的单调右边界.

---

1. 题目大意：有N个人，顺序排列，他们的身高分别为H[i],每个人向自己后方看，他能看到的人是在他后面离他最近并且比他高的人。请依次输出每个人能看到的人的编号Next[i],如果他后面不存在比他高的人，则输出-1。
   此题的解法与直方图最大面积的解法相似，只不过单调栈的入栈出栈规则刚好相反
   描诉如下：

• 入栈规则：如果栈顶元素大于当前元素，就入栈
• 出栈规则：否则，栈顶元素大于当前元素，就出栈，记录下出栈元素的next，直到在栈顶元素大于当前元素。

1. POJ 2796
   題目大意：找一个子序列，使得这个序列的和乘以序列中的最小值的乘积最大。
   显然，这也是个单调栈的问题。

   #include <stdio.h>
   #define SIZE 6
   int array[SIZE] = {3,1,6,4,5,2};
   
   typedef struct t{
   	int value;
   	int startIndex;
   }node;
   
   int main(){
   
   	/*初始化栈*/
   	node stack[SIZE + 1];
   	int sum[SIZE];
   	int top = 0;
   	stack[0].value = 0;
   	stack[0].startIndex = 0;
   	top++;
   	/**/
   	int m_sum;
   	int result;
   	int max_mul = 0;
   	int i, j;
   	/**/
   	int index;
   	sum[0] = array[0];
   	/*计算前n (0:SIZE-1)个数的和*/
   	for (i = 1; i< SIZE; i++){
   		sum[i] = sum [i-1]+array[i];
   	}
   	for (index = 0; index < SIZE; index++){
   		if (array[index] >= stack[top -1].value){
   			stack[top].value = array[index];
   			stack[top].startIndex = index;
   			top++;
   		}else{
   			while(array[index] < stack[top - 1].value && top > 1){
   				/*for( sum = 0, j = stack[top -1].startIndex; j < index; j++){					sum += array[j];				}*/
   					sum += array[j];
   				}*/
   				m_sum = sum[index -1] - sum [stack[top -1].startIndex -1];
   				result = m_sum * stack[top - 1].value;
   				if (result > max_mul)
   					max_mul = result;
   				top--;
   			}
   			stack[top].value = array[index];
   			top++;
   		}
   	}
   	while(top > 1){
   		m_sum = sum[index -1] - sum [stack[top -1].startIndex -1];
   		result = m_sum * stack[top -1].value;
   		if (result > max_mul)
   			max_mul = result;
   		top--;
   	}
   	printf("the maximum multile is %d\n", max_mul);
   	return 0;
   }

2. 给个数组，返回一个数组，返回数组的每个元素是原数组中右边的第一个大于该位置元素的索引。

应用单调栈，当入栈的元素大于栈顶的元素时，就把栈顶元素的相应的结果设为当前要入栈的元素的索引，直到栈顶元素对应的值大于索引
当右边没有比他大的元素时，返回-1;

vector<int> indexOfFirstLargeElments(vector<int> nums){
	if(nums.empty())
		return {};
	vector<int> ret(nums.size(), -1);
	
	stack<int> s;
	for(int i = 0; i < nums.size(); i++){
		while(!s.empty() && nums[i] > nums[s.top()]){
			ret[s.top()] = i;
			s.pop();
		}
		s.push(i);
	}
	return ret;
}